
# 模板

# node节点
class Node:
    # 限制Node类的实例只有这两个属性
    __slots__ = 'son', 'end'

    def __init__(self):
        self.son = {}
        self.end = False

class Trie:
    def __init__(self):
        #  初始化root 根节点
        self.root = Node()

    def insert(self, word: str) -> None:
        # 从根节点出发
        cur = self.root
        for c in word:
            if c not in cur.son:
                # 为c 创建一个节点
                cur.son[c] = Node()
            # 当前节点更新到创建的那一个接待你
            cur = cur.son[c]
        # 遍历完后 添加是否是当前字母的结束
        cur.end = True

    def find(self, word: str) -> int:
        # 从根节点出发
        cur = self.root
        for c in word:
            # 找不到
            if c not in cur.son:
                return 0
            # 找到 继续下一个查找
            cur = cur.son[c]
        return 2 if cur.end else 1

    # 搜索wrod是否在字典树里面
    def search(self, word: str) -> bool:
        return self.find(word) == 2

    # 是否 以prefix 开始的字母
    def startsWith(self, prefix: str) -> bool:
        return self.find(prefix) != 0

